﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//[53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/)
class Solution
{
public:
	//推导状态转移方程
	//dp[i]表示：以i位置为结尾，所有子数组的最大和
	//dp[i] = nums[i] 或者dp[i] = dp[i-1] + nums[i]
	//即:dp[i] = max(nums[i],dp[i-1]+nums[i])
	//初始化：开一个辅助位dp[0] = 0;
	int maxSubArray(vector<int>& nums)
	{
		int n = nums.size();
		//建立dp表
		vector<int>dp(n + 1);
		int ret = -0x3f3f3f3f;

		for (int i = 1; i <= n; i++)
		{
			//从左到右填表
			dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
			ret = max(ret, dp[i]);
		}

		//返回值
		return ret;
	}
};


//[918. 环形子数组的最大和] (https://leetcode.cn/problems/maximum-sum-circular-subarray/)

class Solution
{
public:
	//推导状态转移方程
	//dp[i]表示：以第i哥位置为结尾，所有子数组的最大和
	//额外条件：由于是环状结构，我们需要分开讨论
	//1.f表示：求所有子数组中的最大和
	//2.g表示：求所有子数组中的最小和，但是我们不是需要的子数组中的最小和，而是数组总和减去最小和
	//得到环形结构中的最大和
	//画图笔记：再动态规划专题中的markdown笔记中

	int maxSubarraySumCircular(vector<int>& nums)
	{
		int n = nums.size();
		vector<int>f(n + 1);
		vector<int>g(n + 1);
		int sum = 0;
		int ret1 = -0x3f3f3f3f;
		int ret2 = 0x3f3f3f3f;
		for (int i = 1; i <= n; i++)
		{
			sum += nums[i - 1];
			//注意nums的下标映射关系，因为多开了一个辅助位
			f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
			g[i] = min(g[i - 1] + nums[i - 1], nums[i - 1]);
			ret1 = max(ret1, f[i]);
			ret2 = min(ret2, g[i]);
		}

		//返回值
		//处理整个数组中都为负的情况
		return sum == ret2 ? ret1 : max(ret1, sum - ret2);
	}
};

//152. 乘积最大子数组❤️](https://leetcode.cn/problems/maximum-product-subarray/)
class Solution
{
public:
	//推导状态转移方程
	//以i为结尾，数组中乘积最大的子数组
	//由于一个状态表示不了乘积我们需要开两个状态表
	//f[i]表示:以i为结尾，数组中乘积最大的子数组
	//g[i]表示:以i为结尾，数组中乘积最小的子数组
	//具体状态表示再动态规划专题的markdown画图笔记中
	//f[i] = max(nums[i],max(f[i-1] * nums[i],g[i-1] * nums[i]))
	//g[i] = max(nums[i],max(f[i-1] * nums[i],g[i-1] * nums[i]))

	int maxProduct(vector<int>& nums)
	{
		int n = nums.size();
		vector<int>f(n + 1);
		vector<int>g(n + 1);
		//初始化，注意细节，乘积辅助位不能为0
		f[0] = 1, g[0] = 1;
		int ret = -0x3f3f3f3f;
		for (int i = 1; i <= n; i++)
		{
			f[i] = max(nums[i - 1], max(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));
			g[i] = min(nums[i - 1], min(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));
			ret = max(ret, f[i]);
		}
		return ret;
	}
};